/**
 * 
 */
package search;

import java.util.Collection;
import java.util.LinkedList;
import java.util.Vector;
import java.io.*;

/**
 * @author dbs
 *
 */
class SearchAdapter implements ISearch {
  protected IHeuristic heuristic;
  protected int currentDepthLimit = 0, maxDepthLimit = 1000, beamWidth = 0;
  LinkedList<Vector<INode>> queue = new LinkedList<Vector<INode>>();
  LinkedList<Vector<INode>> deadEnds = new LinkedList<Vector<INode>>();
  Vector<INode> solution;
  DataOutputStream log;

  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    return null;
  }

  protected void InsertIntoQueue (LinkedList<Vector<INode>> queue, Vector<INode> path) {
    queue.add (path);
  }

  public void SetHeuristic (IHeuristic h) {
    heuristic = h;
  }

  public void SetInitialDepthLimit (int limit) {
    currentDepthLimit = limit;
  }

  public void SetMaximumDepthLimit (int limit) {
    maxDepthLimit = limit;
  }

  public void SetBeamWidth (int limit) {
    beamWidth = limit;
  }

  public void SetLogFile (DataOutputStream l) {
    log = l;
  }

  public Vector<INode> GetSolution () {
    return solution;
  }

  public int GetSolutionCost () {
    if (solution!=null) {
      int path_cost = 0;
      for (int i = 0; i < solution.size()-1; ++i) {
        path_cost += solution.get(i).GetPathCost(solution.get(i+1));
      }
      return path_cost;
    }
    return -1;
  }

  public LinkedList<Vector<INode>> GetPartialPaths() {
    queue.addAll (deadEnds);
    return queue;
  }

  public int GetQueueSize () {
    return queue.size();
  }

  protected int GetExplorablePathCount (LinkedList<Vector<INode>> queue) {
    return queue.size();
  }

	/* (non-Javadoc)
	 * @see search.ISearch#Search(search.INode, search.INode, java.util.Collection)
	 */
	public boolean Search(INode start, INode end, Collection<INode> path) {
		LinkedList<INode> explored = new LinkedList<INode>();
		Vector<INode> startPath = new Vector<INode>();
		startPath.add(start);
		queue.add(startPath);
		while(GetExplorablePathCount(queue) > 0) {
			Vector<INode> partialPath = ChoosePath(queue);
			if (partialPath.lastElement() == end) {
				path.addAll(partialPath);
        solution = partialPath;
				return true;
			}
			explored.add(partialPath.lastElement());
			Expand(partialPath, explored, queue);
		}
    return false;
	}
	
	public void Expand (Vector<INode> partialPath, LinkedList<INode> explored, LinkedList<Vector<INode>> queue) {
    try {
      INode node = partialPath.lastElement ();
      Collection<INode> connNodes = node.GetConnectedNodes ();
      if (log!=null) log.writeBytes("\n"+node.toString()+"\t");
      int counter = 0; // for the sake of printing a space
      for (INode child: connNodes) {
        if (log!=null) log.writeBytes(child.toString());
        if (explored.contains(child)) {
          continue;
        }
        Vector<INode> newPath = new Vector<INode>(partialPath);
        newPath.add(child);
        InsertIntoQueue (queue, newPath);
        if (++counter < connNodes.size()) if (log!=null) log.writeBytes(" ");
      }
      // If none of the nodes in the list are traversable, then we have a dead end.
      // In that case, counter will be zero.
      if (counter==0) {
        deadEnds.add (partialPath);
      }
      if (log!=null) log.writeBytes("\t"+GetQueueSize());
    } catch (IOException e) {
      System.err.println ("Error writing to file while writing step information");
      System.err.println ("Please check the log file permissions");
    }
	}
}

class BreadthFirstSearch extends SearchAdapter {
  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    return queue.removeFirst ();
  }
}

class BeamSearch extends BreadthFirstSearch {
  protected void InsertIntoQueue (LinkedList<Vector<INode>> queue, Vector<INode> path) {
    // TODO: confirm if this is the right approach
    int h = heuristic.Heuristic(path.lastElement());
    if (queue.size() >= beamWidth) {
      if (h >= heuristic.Heuristic(queue.getLast().lastElement())) {
        // as this new element's heuristic is greater than the max in the
        // queue, let's not bother
        return;
      } else {
        for (int i = queue.size() - 1; i >= 0; --i) {
          if (heuristic.Heuristic(queue.get(i).lastElement()) > h) {
            queue.set(i, path);
          }
        }
      }
    } else {
      // if the size of queue is less than the specified
      // beam width, let's insert the path at the suitable
      // position
      int index = 0;
      for (int i = queue.size() - 1; i >= 0; --i) {
        if (heuristic.Heuristic(queue.get(i).lastElement()) > h) {
          index = i;
        }
      }
      queue.add(index, path);
    } 
  }
}

class DepthFirstSearch extends SearchAdapter {
  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    return queue.removeLast ();
  }
}

class BestFirstSearch extends SearchAdapter {
  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    int leastValuedNode = -1, leastValue = 1000000;
    int count = 0;
    for (Vector<INode> node: queue) {
      int h = heuristic.Heuristic(node.lastElement());
      if (h<leastValue) {
        leastValue = h;
        leastValuedNode = count;
        ++count;
      }
    }
    return queue.remove (leastValuedNode);
  }
}

class BiDirectionalSearch extends SearchAdapter {
  LinkedList<Vector<INode>> endQueue = new LinkedList<Vector<INode>> ();

  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    return queue.removeFirst ();
  }

  public LinkedList<Vector<INode>> GetPartialPaths() {
    LinkedList<Vector<INode>> biQueue = new LinkedList<Vector<INode>>();
    biQueue.addAll (queue);
    biQueue.addAll (endQueue);
    biQueue.addAll (deadEnds);
    return biQueue;
  }

  public int GetQueueSize () {
    return queue.size()+endQueue.size();
  }

  public boolean Search (INode start, INode end, Collection<INode> path) {
		LinkedList<INode> exploredFromStart = new LinkedList<INode>();
		Vector<INode> startPath = new Vector<INode>();
		startPath.add(start);
		queue.add(startPath);

		LinkedList<INode> exploredFromEnd = new LinkedList<INode>();
		Vector<INode> endPath = new Vector<INode>();
		endPath.add(end);
		endQueue.add(endPath);
    while (GetExplorablePathCount(queue) > 0 && 
            GetExplorablePathCount(endQueue) > 0) {
      if (GetExplorablePathCount(queue) > 0) {
        Vector<INode> partialPath = ChoosePath(queue);
        if (partialPath.lastElement() == end) {
          path.addAll(partialPath);
          if (solution == null) solution = new Vector<INode>();
          solution.addAll (path);
          return true;
        } else {
          for (Vector<INode> endNodes: endQueue) {
            if (endNodes.lastElement() == partialPath.lastElement()) {
              path.addAll (partialPath);
              for (int i = endNodes.size()-2; i >=0; --i) path.add (endNodes.get(i));
              if (solution == null) solution = new Vector<INode>();
              solution.addAll (path);
              return true;
            }
          }
        }
        exploredFromStart.add(partialPath.lastElement());
        Expand(partialPath, exploredFromStart, queue);
      }

      if (GetExplorablePathCount(endQueue) > 0) {
        Vector<INode> partialPath = ChoosePath(endQueue);
        for (Vector<INode> startNodes: queue) {
          if (startNodes.lastElement() == partialPath.lastElement()) {
            path.addAll (startNodes);
            for (int i = partialPath.size()-2; i >=0; --i) path.add (partialPath.get(i));
            if (solution == null) solution = new Vector<INode>();
            solution.addAll (path);
            return true;
          }
        }
        exploredFromEnd.add(partialPath.lastElement());
        Expand(partialPath, exploredFromEnd, endQueue);
      }
    }
    return false;
  }
}

class IterativeDeepeningSearch extends SearchAdapter {
  protected int GetExplorablePathCount (LinkedList<Vector<INode>> queue) {
    int count = 0;
    for (Vector<INode> node: queue) {
      if (node.size() <= currentDepthLimit) ++count;
    }
    return count;
  }
  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    for (int i = queue.size()-1; i >= 0; --i) {
      if (queue.get(i).size() <= currentDepthLimit) return queue.remove(i);
    }
    System.err.println("ERROR:ChoosePath return line in IDS should never get called!");
    return null;
  }

  public boolean Search (INode start, INode end, Collection<INode> path) {
    boolean searchSuccessful = false;
    while (currentDepthLimit<maxDepthLimit) {
      if (super.Search(start, end, path)) {
        searchSuccessful = true;
        solution.addAll (path);
        break;
      }
      path.clear ();
      ++currentDepthLimit;
    }
    return searchSuccessful;
  }
}

class AStarSearch extends SearchAdapter {
  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    int leastValuedNode = -1, leastValue = 100000000;
    int count = 0;
    for (Vector<INode> nodes: queue) {
      int h = heuristic.Heuristic(nodes.lastElement());
      if (nodes.size() > 1) {
        h += nodes.lastElement().GetPathCost (nodes.get(nodes.size()-2));
      }
      if (h<leastValue) {
        leastValue = h;
        leastValuedNode = count;
      }
      ++count;
    }
    return queue.remove (leastValuedNode);
  }
}

class IDAStarSearch extends SearchAdapter {
  protected int GetExplorablePathCount (LinkedList<Vector<INode>> queue) {
    int count = 0;
    for (Vector<INode> node: queue) {
      if (node.size() <= currentDepthLimit) ++count;
    }
    return count;
  }
  protected Vector<INode> ChoosePath (LinkedList<Vector<INode>> queue) {
    int leastValuedNode = -1, leastValue = 1000000;
    int count = 0;
    for (Vector<INode> nodes: queue) {
      if (nodes.size() > currentDepthLimit) continue;
      int h = heuristic.Heuristic(nodes.lastElement());
      if (nodes.size() > 1) {
        h += nodes.lastElement().GetPathCost (nodes.get(nodes.size()-2));
      }
      if (h<leastValue) {
        leastValue = h;
        leastValuedNode = count;
      }
      ++count;
    }
    if (leastValuedNode >= 0) return queue.remove (leastValuedNode);
    else {
      System.err.println("ERROR:ChoosePath return line in IDAS should never get called!");
      return null;
    }
  }
  public boolean Search (INode start, INode end, Collection<INode> path) {
    boolean searchSuccessful = false;
    while (currentDepthLimit<maxDepthLimit) {
      if (super.Search(start, end, path)) {
        searchSuccessful = true;
        solution.addAll (path);
        break;
      }
      path.clear ();
      ++currentDepthLimit;
    }
    return searchSuccessful;
  }
}

public class SearchFactory {
	public static ISearch CreateSearch (SearchMethod method) {
		switch(method) {
		case BREADTH_FIRST:
			return new BreadthFirstSearch();
    case DEPTH_FIRST:
      return new DepthFirstSearch();
    case BEST_FIRST:
      return new BestFirstSearch();
    case BIDIRECTIONAL:
      return new BiDirectionalSearch();
    case BEAM:
      return new BeamSearch();
    case ITERATIVE_DEEPENING:
      return new IterativeDeepeningSearch();
    case ASTAR:
      return new AStarSearch();
    case ID_ASTAR:
      return new IDAStarSearch();
		default:
			break;
		}
		return null;
	}
}
